import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        if(matrix == null) return null;
        List<Integer> result = new ArrayList<Integer>();
        
        int m = matrix.length;
        if(m == 0) return result;
        int n = matrix[0].length;
        if(n==0) return result;

        int startx = 0;
        int starty = 0;

        int xVisited = 0;
        int yVisited = 0;

        int[] x = {1,0,-1,0};
        int[] y = {0,1,0,-1};

        int direction = 0;
        int step = 0;
        int candidateMove = 0;

        while(true){
            if(x[direction]==0)
                candidateMove = m - yVisited;
            else
                candidateMove = n - xVisited;

            if(candidateMove<=0)
                break;

            System.out.println(startx + " " + starty + " " + candidateMove);
            result.add(matrix[starty][startx]);

            step++;

            if(candidateMove == step){
                yVisited += x[direction] == 0 ? 0: 1;
                xVisited += y[direction] == 0 ? 0: 1;
                direction = (direction + 1)%4;

                step = 0;
            }

            startx += x[direction];
            starty += y[direction];
        }

        return result;
    }
    
    public static void main(String[] args) {
        int[][] m = new int[3][4];

        int index = 1;
        for(int i=0;i<m.length;i++){
            for(int j=0;j<m[0].length;j++){
                m[i][j]= index++;
            }
        }

        for(int i=0;i<m.length;i++){
            for(int j=0;j<m[0].length;j++){
                //matrix[i][j]= index++;
                System.out.print(m[i][j] + "\t");
            }
            System.out.println();
        }

        System.out.println();
        
        List<Integer> r = spiralOrder(m);

        for(int i : r){
            System.out.print(i + "\t");
        }
    }
}
